package com.leetcode.easy;

import com.leetcode.entity.TreeNode;

/**
 * @Classname SortedArrayToBST
 * @Description 有序数组转化为二叉搜索树
 * 一个高度平衡的二叉搜索树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
 * @Date 2020/9/18 9:19
 * @Created by zfl
 *
 */
public class SortedArrayToBST {
    /**
     * @param nums
     * @return TreeNode
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.7 MB, 在所有 Java 提交中击败了85.46%的用户
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

}
